A18 - Subset Sum

提出

code: python

n, s = map(int, input().split())

a = list(map(int, input().split()))

# O(pow(2, n))

# dpij := i 枚で合計 j にできるか

dp = [0 * (s+1) for _ in range(n+1)]

for v in a:

dp1v = 1

# print(dp)

# 0, 0, 0, 0, 0, 0, 0, 0], 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, [0, 0, 0, 0, 0, 0, 0, 0

for i in range(2, n+1):

pass

# 個数制限あり

解答

code: python

n, s = map(int, input().split())

a = list(map(int, input().split()))

# 2 2 3

# dpij := ai まででどれか選び、合計 j にできるか

dp = [0 * (s+1) for _ in range(n+1)]

dp00 = True

for i in range(1, s+1):

dp0i = False

for i in range(1, n+1):

for j in range(0, s+1):

# i を選ばない

if dpi-1j == True:

dpij = True

# i を選ぶ

elif j >= ai-1 and dpi-1[j-ai-1] == True:

dpij = True

else:

dpij = False

if dpns == True:

print("Yes")

else:

print("No")